import java.util.*;

abstract class Graph<V> {
  public Graph() {
  }

  public abstract List<EdgeInfo<V>> getEdgesFrom(V begin);

  public abstract void addVertex(V v);

  public abstract void addEdge(V from, V to);

  public static class EdgeInfo<V> {
    private V from;
    private V to;

    public EdgeInfo(V from, V to) {
      setFrom(from);
      setTo(to);
    }

    public V getFrom() {
      return from;
    }

    public void setFrom(V from) {
      this.from = from;
    }

    public V getTo() {
      return to;
    }

    public void setTo(V to) {
      this.to = to;
    }
  }
}

public class ListGraph<V> extends Graph<V> {
  public ListGraph() {
    super();
  }

  private static class Vertex<V> {
    V value;
    Set<Edge<V>> inEdges = new HashSet<>();
    Set<Edge<V>> outEdges = new HashSet<>();

    Vertex(V value) {
      this.value = value;
    }

    @Override
    public boolean equals(Object obj) {
      return Objects.equals(value, ((Vertex<V>) obj).value);
    }

    @Override
    public int hashCode() {
      return value == null ? 0 : value.hashCode();
    }
  }

  private static class Edge<V> {
    Vertex<V> from;
    Vertex<V> to;

    Edge(Vertex<V> from, Vertex<V> to) {
      this.from = from;
      this.to = to;
    }

    public EdgeInfo<V> info() {
      return new EdgeInfo<>(from.value, to.value);
    }

    @Override
    public boolean equals(Object obj) {
      var edge = (Edge<V>) obj;
      return Objects.equals(from, edge.from) && Objects.equals(to, edge.to);
    }

    @Override
    public int hashCode() {
      return from.hashCode() * 31 + to.hashCode();
    }

  }

  private final Map<V, Vertex<V>> vertices = new HashMap<>();

  @Override
  public void addVertex(V v) {
    if (vertices.containsKey(v)) return;
    vertices.put(v, new Vertex<>(v));
  }

  @Override
  public void addEdge(V from, V to) {
    var fromVertex = vertices.get(from);
    if (fromVertex == null) {
      fromVertex = new Vertex<>(from);
      vertices.put(from, fromVertex);
    }

    var toVertex = vertices.get(to);
    if (toVertex == null) {
      toVertex = new Vertex<>(to);
      vertices.put(to, toVertex);
    }

    var edge = new Edge<>(fromVertex, toVertex);
    if (fromVertex.outEdges.remove(edge)) {
      toVertex.inEdges.remove(edge);
    }
    fromVertex.outEdges.add(edge);
    toVertex.inEdges.add(edge);
  }

  @Override
  public List<EdgeInfo<V>> getEdgesFrom(V begin) {
    var vertex = vertices.get(begin);
    if (vertex == null) return new ArrayList<>();
    return vertex.outEdges.stream().map(Edge::info).toList();
  }

}
